/*3、用希尔排序和快速排序算法进行排序。
要求列出排序中的数据元素交换过程。*/

#include<stdio.h>

void show_shell_sort_verbose(int* a,int n){
    printf("----- Shell Sort -----\n");
    int i,j,k,l,d,cur;
    d = n;
    while(d>1){
        d /= 2;
        printf("d=%d:\n",d);
        for(k=0;k<d;k++){ // d组，做d次插入排序，甚至可以直接套上面的代码
            printf("    k=%d :",k);
            for(i=k;i<n;i+=d){
                cur = a[i];
                for(j=k;j<i;j+=d)if( cur<a[j] )break;
                if(j<i)for(l=i;l>j;l-=d)a[l]=a[l-d];
                a[j] = cur;
            }
            for(i=k;i<n;i+=d)printf("%d ",a[i]);putchar('\n');
        }
    }
}

void quick_sort_verbose(int* a,int n){
    if (n == 0 || n == 1)return;
    int i,j,k,tmp,cur;
    printf("-> [quicksort size %d: ",n);
    for(k=0;k<n;k++)printf("%d ",a[k]);putchar(']');putchar('\n');
    cur = a[0]; i = 0; j = n-1;
    while(i!=j){
        if( (i<j && a[i]>a[j]) || (i>j && a[i]<a[j]) ){
            printf("[Swap %d,%d] ",a[i],a[j]);
            tmp = a[i];a[i]=a[j];a[j]=tmp;
            tmp = i; i = j; j = tmp;
            for(k=0;k<n;k++)printf("%d ",a[k]);putchar('\n');
        }
        if(i<j)--j;else ++j;
    }
    quick_sort_verbose(a,i);
    quick_sort_verbose(a+i+1,n-i-1);
}


int main(int argc,char** argv){
    int shell[] = { 58, 43 ,72 ,90 ,12 ,35, 68 ,65, 28 ,95 ,20 };
    int quick[] = { 58, 43 ,72 ,90 ,12 ,35, 68 ,65, 28 ,95 ,20 };
    int NUM_SIZE = 11;
    show_shell_sort_verbose(shell,NUM_SIZE);
    printf("----- Quick Sort -----\n");
    quick_sort_verbose(quick,NUM_SIZE);
    for(int i=0;i<NUM_SIZE;i++)printf("%d ",shell[i]);putchar('\n');
    return 0;
}
